W10. Nondeterminism and Computability

1. Theory

1.1 Determinism vs. Nondeterminism

1.1.1 Deterministic Computation

A Deterministic Finite State Automaton (DFSA) is the classical model in which every state-input pair maps to exactly one next state. Formally, a DFSA is a 5-tuple where:

• is a finite set of states;
• is a finite input alphabet;
• is a total transition function — for every state and every input symbol, the next state is uniquely determined;
• is the initial state;
• is the set of accepting states.

The transition function is total: it is defined for every pair . This means a DFSA never gets stuck — it always has exactly one transition to follow.

1.1.2 Nondeterministic Computation

Nondeterminism extends the deterministic model by allowing, from a single state on a single input symbol, zero, one, or more possible transitions. Rather than following one fixed path, a nondeterministic machine conceptually explores all branches simultaneously.

A Nondeterministic Finite State Automaton (NFSA) (also written NDFSA) is a tuple where all components are as in a DFSA, except:

where denotes the power set of — the set of all subsets of . The transition function now returns a set of successor states (possibly empty, possibly containing more than one state).

Deterministic (left) vs. nondeterministic (right) transitions from q₀

The key intuition is that nondeterminism models parallel exploration: the machine simultaneously pursues every possible transition. In terms of implementation, think of it as forking a thread for each possible next state.

1.1.3 The Extended Transition Function

For both deterministic and nondeterministic automata, we extend the transition function from single symbols to whole strings.

For an NFSA , the extended transition function is defined inductively:

1. For every : — reading the empty string leaves the machine in the same state.
2. For every , , and : That is, after reading the machine is in some set of states; reading one more symbol applies to each of those states and takes the union of all resulting sets.

Example. Suppose , , . Then:

1.1.4 Acceptance Condition for an NFSA

A string is accepted by an NFSA if and only if at least one of the states reachable after reading is an accepting state:

This is called existential nondeterminism: it is sufficient that one computation path leads to an accepting state. If even one branch succeeds, the string is accepted.

There is also a universal interpretation (used in different contexts): , meaning all reachable states must be accepting. The standard NFSA uses the existential interpretation.

1.1.5 NFSA with -Transitions

An -NFSA extends the NFSA by allowing transitions on the empty string . The transition function becomes:

An -closure of a state is the set of all states reachable from using only -transitions (zero or more), including itself:

The extended transition function for -NFSAs is modified so that after reading any real symbol, the machine also follows all reachable -transitions:

-transitions are not strictly necessary — any -NFSA can be converted to an equivalent NFSA without -transitions — but they often make automata design significantly simpler (especially in Thompson’s Construction for regular expressions).

1.2 Equivalence of DFSA and NFSA

One of the fundamental results of automata theory is that DFSA and NFSA recognize exactly the same class of languages — the regular languages. Nondeterminism does not add expressive power for finite automata; it only offers a convenience for design.

1.2.1 Subset Construction Algorithm

Given an NFSA , the equivalent DFSA is constructed as follows:

• — each state of the DFSA corresponds to a subset of NFSA states (hence the name subset construction or powerset construction).
• — the DFSA starts in the singleton set containing the NFSA’s initial state.
• — a DFSA state is accepting if it contains at least one NFSA accepting state.
• for each and .

Stepwise procedure:

1. Build the NFSA transition table.
2. Create a DFSA table; mark the start state as .
3. For each DFSA state (which is a set of NFSA states) and each input symbol, compute by unioning the NFSA transitions from all states in the set.
4. Each new set computed in step 3 that has not been seen before becomes a new DFSA state; repeat step 3 for it.
5. Terminate when no new DFSA states are produced.
6. Mark all DFSA states that contain an NFSA accepting state as accepting.

Worst-case cost: If the NFSA has states, the DFSA may need up to states. In practice, many subsets are unreachable and the actual number is often much smaller.

1.2.2 Why Use NFSA if They Add No Power?

Even though NFSAs recognize no more languages than DFSAs, they are valuable for two reasons:

• Ease of design. An NFSA for a pattern is often far simpler to construct. For example, the NFSA recognizing strings containing the substring is a linear chain of 7 states, while the equivalent DFSA requires careful handling of every possible partial match failure.
• Exponential state compression. An NFSA with states can represent a language whose minimal DFSA requires states. NFSAs are therefore an important intermediate representation in compiler construction (lexical analysis) and pattern matching.

1.3 Regular Expressions

Regular expressions (RegExps) were introduced by Stephen Kleene as a compact algebraic notation for describing regular languages. They are used ubiquitously in text search, compilers, and formal verification.

1.3.1 Syntax and Inductive Definition

A regular expression over an alphabet is defined inductively:

Basis:

• is a RegExp, denoting the empty language .
• is a RegExp, denoting — the language containing only the empty string.
• Each symbol is a RegExp, denoting .

Induction. If and are RegExps, then:

• is a RegExp: union, .
• is a RegExp (dot often omitted): concatenation, .
• is a RegExp: Kleene star, .

The additional notation denotes one or more repetitions: .

1.3.2 Operator Precedence

When parentheses are omitted, operations are evaluated in this order (highest to lowest priority):

1. (Kleene star)
2. (concatenation)
3. (union)

So is parsed as , which denotes .

1.3.3 Examples

• any string over
• = strings over that start or end with 0.

1.4 Thompson’s Construction: RegExp to NFSA

Thompson’s Construction is an algorithm that systematically converts any regular expression into an -NFSA. Each structural component of the RegExp maps to a small, standard NFA fragment.

1.4.1 Base Cases

For a single symbol : create two states (start) and (accepting) with a single transition .

1.4.2 Concatenation:

Connect the accepting state of to the start state of via an -transition. The overall machine starts at the start of and accepts at the accepting state of .

1.4.3 Union:

Create a new start state and a new accepting state . Add -transitions and (to the starts of and ), and and (from their accepting states).

1.4.4 Kleene Star:

Create a new start state and a new accepting state . Add:

• (enter the inner machine),
• (bypass, for zero repetitions),
• (loop back for additional repetitions),
• (exit).

1.4.5 -Elimination (Simplification)

After Thompson’s Construction, the resulting NFSA often contains redundant -transitions. These can be eliminated: if a state has only an -transition to , and is otherwise unremarkable, it can often be merged with . This produces a smaller, cleaner NFSA without affecting the recognized language.

1.5 Historical Background of Turing Machines

The Turing Machine emerged from a profound philosophical and mathematical crisis in the early 20th century.

1.5.1 Principia Mathematica and Logicism

In 1910–1913, Bertrand Russell and Alfred North Whitehead published the Principia Mathematica — a monumental 2,000-page attempt to axiomatize all of mathematics from pure logical principles. The project embodied logicism: the philosophical thesis that mathematical truths are reducible to, and derivable from, pure logic. The authors claimed their system was both complete (every mathematical truth could be derived) and consistent (no falsehood could be derived).

1.5.2 Gödel’s Incompleteness Theorems (1931)

Kurt Gödel shattered the logicist program. In 1931, he proved his Incompleteness Theorems: in any sufficiently powerful logical system, there exist statements that are true but cannot be proven within the system. No consistent formal system powerful enough to describe arithmetic can prove all arithmetic truths. Gödel’s result showed that the goals of Principia Mathematica were unachievable: completeness and consistency cannot coexist for sufficiently rich systems.

1.5.3 Hilbert’s Entscheidungsproblem (1928)

David Hilbert, also committed to the formalization of mathematics, posed the Entscheidungsproblem (German: decision problem) in 1928: is there an algorithm that, given any mathematical proposition and a set of axioms, decides whether that proposition is provable from the axioms? Hilbert called it “the fundamental problem of mathematical logic” — an affirmative answer would reduce all of mathematics to mechanical calculation.

1.5.4 Church and Turing’s Negative Answer (1936)

In 1936, independently, Alonzo Church (using -calculus) and Alan Turing (using his machine model) proved that no such general algorithm exists — the Entscheidungsproblem has a negative answer. To give a rigorous proof of this impossibility, Turing had to first define precisely what an algorithm is. His answer was the Turing Machine.

Turing’s key insight was to model the mechanical process of following rules: a human mathematician, he argued, is essentially a machine that reads symbols, maintains a finite amount of state, and applies rules. By formalizing this as a mathematical object, he could then prove precise limitations.

1.5.5 The Church–Turing Thesis

The Church–Turing thesis (not a theorem, but a widely accepted conjecture) states that:

Any computation that can be carried out by any realizable physical process can be computed by a Turing Machine (equivalently, expressed in -calculus).

This thesis equates the informal notion of “effectively computable” with the formal notion of “Turing-computable.” It is the foundation of modern computability theory.

1.5.6 Turing’s Philosophical Contribution

Before Turing, the prevailing view was idealist: through pure mathematical reasoning, the human mind accesses a Platonic realm of eternal truths. After Turing, the view became materialist: the Turing Machine is a model of the human mathematician. The limits of the machine are the limits of mathematical reasoning. Mathematics is grounded in what the physical world allows — not in a transcendent Platonic domain. Turing’s work marked a fundamental epistemological break in the philosophy of mathematics.

1.6 Turing Machines: Architecture and Formal Definition

1.6.1 Components of a Turing Machine

A Turing Machine (TM) consists of:

• An input tape: a read-only, one-directional sequence of cells containing the input string, followed by blank cells.
• A control device (finite state control): maintains the current state and specifies transitions.
• Memory tapes ( tapes): read/write tapes with a movable head; each cell holds a symbol from the memory alphabet . The memory tapes are non-destructive — writing to a cell does not erase other cells.
• An output tape: a write-only tape.

The key distinction from a PDA is memory persistence: the TM can re-read previously written memory symbols, whereas a PDA’s stack destroys symbols on pop.

1.6.2 Formal Definition

A TM with memory tapes is a 7-tuple where:

• : finite set of states;
• : input alphabet (symbols on the input tape);
• : memory alphabet (symbols writable on memory tapes; and may differ);
• : transition function;
• : initial state;
• : initial memory symbol (initially fills each memory tape — analogous to the bottom-of-stack marker);
• : set of accepting states.

1.6.3 The Transition Function

Reading this left to right:

• Domain: The machine is in a non-accepting state, has read one symbol from the input tape, and one symbol from each of the memory tapes.
• Codomain: The machine transitions to a new state, writes a new symbol on each memory tape, and moves each of the heads (one input head plus memory heads).

The three head movement directions are:

• — move right
• — move left
• — stay in place

A transition is depicted graphically as an edge labeled: where is the input symbol read, is the symbol read from memory tape , is the symbol written to memory tape , is the direction of the input head, and is the direction of memory head .

1.7 Turing Machine Examples

1.7.1 Recognizing

The language cannot be recognized by any PDA (the stack is destructive; once it counts the ’s to match the ’s, those counts are gone and cannot be used to verify the ’s). A TM handles it using a memory tape:

1. Read each from the input and write an on the memory tape (store markers).
2. When all ’s are read, move left on the memory tape and start reading ’s. For each , consume one from memory (move left).
3. When we’ve consumed all ’s (reached ) and the input shows a , move right on the memory tape and start reading ’s, consuming one per .
4. Accept when both the input and the memory tape are fully consumed simultaneously.

This works because the memory tape is persistent — the markers remain until explicitly moved past, so the count of ’s is available for verifying both ’s and ’s.

1.7.2 Recognizing

For :

1. For each read, write two ’s on the memory tape (so the tape holds ’s total).
2. Read ’s from the input while consuming ’s leftward on the memory tape (one per ), verifying ’s.
3. Read the final ’s while consuming ’s rightward on the memory tape (consuming the tape a second time for the trailing ’s).
4. Accept when both tapes are exhausted simultaneously.

1.7.3 Recognizing

The TM stores ’s, then counts the first ’s. At that point it either (a) finds the end of input and accepts (the case), or (b) finds more ’s and re-traverses the memory tape to count more (the case), then accepts when both input and memory are exhausted.

1.8 Variants of Turing Machines and Their Equivalence

1.8.1 Single-Tape TM

A single-tape TM uses one tape for input, memory, and output. The tape is unbounded in both directions. Despite this apparent restriction, the single-tape TM is equivalent in expressive power to the multi-tape TM: any multi-tape TM can be simulated by a single-tape TM. The simulation encodes all tapes onto one tape using separator markers, and tracks all head positions. This may incur a polynomial or quadratic slowdown but does not change what can be computed.

1.8.2 Multidimensional-Tape TM

A 2D-tape TM (or -dimensional TM) uses a grid rather than a line as its tape, with a head that can move in up to directions. Again, all such models are equivalent to the standard TM.

1.8.3 Universal Equivalence

All reasonable TM variants (single tape, multi-tape, multi-dimensional, non-deterministic TM, etc.) recognize exactly the same class of languages — the recursively enumerable languages. This robustness is evidence that the TM captures the right notion of computation, as stated by the Church–Turing thesis.

1.9 Closure Properties of Turing Machines

The class of recursively enumerable languages (languages recognized by TMs) is closed under:

• Union: Given TMs and , build a TM that simulates both in parallel; accept if either accepts.
• Intersection: Simulate both in series; accept only if both accept.
• Concatenation: Nondeterministically guess a split point; run on the first part and on the second.
• Kleene star: Nondeterministically guess decompositions; verify each part.

The intuition for union and intersection is that a TM can easily simulate two other TMs in series or in parallel.

Not closed under complement. TMs are not closed under complement. The reason is that a TM that does not accept a string may either reject it (halt in a non-accepting state) or loop forever. Swapping accepting and non-accepting halting states works for loop-free TMs, but cannot handle non-terminating computations.

Loop-free TMs are closed under complement: For TMs that are guaranteed to halt on all inputs (called recursive or decidable), swapping accepting and rejecting states produces a TM for the complemented language. This is the class of recursive languages (a strict subset of the recursively enumerable languages).

1.10 The Language Hierarchy

The following diagram summarizes the Chomsky hierarchy as discussed throughout the course:

The full language hierarchy (Chomsky) with corresponding machine models

Key observations:

• Regular languages (recognized by FSA): only fixed, finite memory — no generic counting to .
• Deterministic CFL (recognized by DPDA): stack memory, but restricted to deterministic transitions.
• Context-free languages (recognized by nondeterministic PDA): stack is destructive; cannot count multiple independent quantities simultaneously.
• Recursive (Decidable) languages: TMs that always halt; closed under complement.
• Recursively enumerable languages: TMs that may loop; not closed under complement.
• Non-Turing-recognizable: languages that no TM can recognize.

The difference between recursive and recursively enumerable languages can be illustrated with C programs:

• The set of C programs that never run into an infinite loop (on any input) is recursive.
• The set of C programs that contain an infinite loop (on at least one input) is recursively enumerable but not recursive — this is related to the Halting Problem.

1.11 The Memory Model Perspective

The choice of memory model determines the expressive power of a computational model:

• FSA — fixed, finite memory: the current state is the only memory. You can only “count” up to the finite number of states. No generic variable .
• PDA — extensible but destructive memory (stack): can count to a variable , but once a symbol is popped from the stack, it is gone. Cannot simultaneously verify two independent counting constraints.
• TM — persistent memory (tape): symbols written to the tape remain and can be re-read. Behaves like the von Neumann architecture (random-access, persistent memory). Can handle any computable language.

1.12 Countability and Undecidability (Spoilers)

An important meta-result motivates why undecidable problems exist:

• The set of all programs (over any fixed programming language) is countably infinite — programs can be listed lexicographically.
• The set of all problems (functions , or equivalently subsets of ) is uncountably infinite (by Cantor’s diagonal argument).

Therefore, there are infinitely more problems than programs. Most problems — in a set-theoretic sense — have no algorithm. However, naturally occurring, well-structured problems are often decidable. The most famous undecidable problem is the Halting Problem: given a program and an input , does halt on ? Turing proved no TM can decide this for all .

---

2. Definitions

• DFSA (Deterministic Finite State Automaton): A 5-tuple with a total transition function ; each state-input pair leads to exactly one next state.
• NFSA (Nondeterministic Finite State Automaton): A 5-tuple with ; each state-input pair may lead to zero, one, or many next states.
• -NFSA: An NFSA whose transition function also allows -transitions: .
• -closure: For a state , is the set of all states reachable from via -transitions alone (including itself).
• Extended transition function : For an NFSA, is the inductive extension of to strings; and .
• Acceptance (NFSA): A string is accepted iff (existential nondeterminism).
• Power set : The set of all subsets of , including and itself.
• Subset construction: Algorithm converting an NFSA to a DFSA by treating sets of NFSA states as individual DFSA states; yields in the worst case.
• Regular expression (RegExp): A formula built from , , alphabet symbols, union (), concatenation (), and Kleene star (); denotes a regular language.
• Kleene star (): The set of all strings formed by concatenating zero or more strings from .
• Thompson’s Construction: Algorithm converting a RegExp to an -NFSA by structural induction on the RegExp.
• Logicism: A philosophy of mathematics holding that mathematical truths are derivable from pure logical principles (Principia Mathematica).
• Gödel’s Incompleteness Theorem: In any sufficiently powerful consistent formal system, there exist true statements that are unprovable within the system (1931).
• Entscheidungsproblem: Hilbert’s 1928 question asking for an algorithm to decide whether any mathematical proposition is provable from given axioms.
• Church–Turing thesis: The conjecture that any effectively computable function is computable by a Turing Machine.
• Turing Machine (TM): A 7-tuple consisting of states, input alphabet, memory alphabet, transition function, initial state, initial memory symbol, and accepting states; uses persistent read/write memory tapes.
• Recursively enumerable language: A language recognized by some TM (the TM may loop on rejected inputs).
• Recursive (decidable) language: A language recognized by a TM that halts on all inputs; closed under complement.
• Halting Problem: The problem of deciding, given a program and input , whether halts on ; proven undecidable by Turing.
• Existential nondeterminism: Acceptance criterion requiring that at least one computation path accepts.
• Universal nondeterminism: Acceptance criterion requiring that all computation paths accept.

---

3. Formulas

• DFSA transition function:
• NFSA transition function:
• -NFSA transition function:
• Extended transition (NFSA, base):
• Extended transition (NFSA, step):
• NFSA acceptance:
• Subset construction — DFSA transition:
• Subset construction — accepting states:
• TM transition function ( tapes):

---

4. Practice

4.1. Build NFSAs for Three Languages (Lab 9, Task 1)

Build NFSAs that recognize the following languages:

Click to see the solution

(a) : strings ending with .

Use the standard suffix-guessing pattern: the NFSA “guesses” the start of the final and then verifies it deterministically.

• : start state, self-loop on ; transition to on (guess: the final starts here).
• : transition to on .
• : transition to on .
• : accepting state (no outgoing transitions needed).

(b) : strings of the form where does not start with and every in is followed by exactly one .

The language consists of a (possibly empty) block of ’s, followed by a pattern where each is paired with exactly one (and no leading ).

• (accepting): self-loop on ; transition to on (enter the part where must be followed by ).
• : transition to (accepting) on .
• (accepting): transition to on (each new in must be followed by a ).

(c) : strings ending with , , or .

Three parallel suffix-detector branches, each two steps long:

• : self-loop on ; transitions to on , to on , to on .
• : transition to (accepting) on (detected ).
• : transition to (accepting) on (detected ).
• : transition to (accepting) on (detected ).
• : single shared accepting state.

Answer: Three simple NFSA designs using the suffix-guessing pattern.

4.2. Convert NFSA to DFSA: Language Ending in 101 (Lab 9, Task 2)

The NFSA for has four states: start state with a self-loop on ; transitions (accepting).

Apply the subset construction algorithm to produce the equivalent DFSA. Write out the full DFSA transition table and identify all accepting states.

Click to see the solution

NFSA transition table:

Subset construction:

Start: .

DFSA state	on	on

The DFSA has 4 states. The only accepting state is (contains ).

Verification: Starting from , reading : ✓ (accepting).

Answer: 4-state DFSA with accepting state .

4.3. Convert NFSA to DFSA: Constrained Language over (Lab 9, Task 3)

The NFSA for has three states: (accepting) with a self-loop on and a transition to on ; transitions to (accepting) on ; transitions back to on .

Apply subset construction to this NFSA and produce the equivalent DFSA.

Click to see the solution

NFSA transition table (accepting states: ):

Subset construction:

Start: (accepting, since ).

DFSA state	on	on

Accepting DFSA states: , , (each contains at least one of ).

Answer: 5-state DFSA. The sink state handles rejected prefixes (e.g., strings starting with ).

4.4. Convert NFSA to DFSA: Strings Ending in , , or (Lab 9, Task 4)

The NFSA for is the one from Task 4.5(c). Apply subset construction and produce the full DFSA transition table.

Click to see the solution

NFSA (from Task 4.5(c)): , accepting: .

Subset construction (reachable states only):

Start: .

DFSA state	on	on	on

Accepting DFSA states: those containing .

Answer: 7-state DFSA. Accepting states are , , and .

4.5. Describe Languages of Regular Expressions (Lab 9, Task 5)

Over , give a concise English description of each language:

Click to see the solution

1. : The empty language — no string is accepted, not even the empty string.
2. : The language containing only the empty string . The Kleene star of the empty set allows zero repetitions of nothing, producing exactly .
3. : All binary strings that contain the substring . The prefix matches any binary string (it generates ); then requires a block of three zeros; then allows any suffix. So the language is .
4. : Strings in which every is immediately preceded by at least one (no leading without a preceding , except the optional leading single covered by the choice). More precisely: an optional leading , followed by zero or more blocks of the form (one or more zeros then a one), followed by zero or more trailing zeros. This is the set of binary strings in which never appears without a preceding , except possibly the very first character.

Answer: (1) empty language; (2) ; (3) strings containing ; (4) strings where every (except possibly the first character) is preceded by at least one .

4.6. Build Regular Expressions over (Lab 9, Task 6)

Construct regular expressions over for:

5. The set of strings consisting of alternating ’s and ’s.
6. The set of strings containing an odd number of ’s.
7. The set of strings ending with and not containing the substring .
8. The set of strings in which both the number of ’s and the number of ’s are even.

Click to see the solution

5. Alternating ’s and ’s.

Alternating strings start with either or and strictly alternate. This gives four possible shapes: , , , and the infinite families starting with or :

Expanded: the string is either empty, or starts with an optional , then zero or more pairs, then an optional trailing . This generates all alternating strings:

6. Odd number of ’s.

Track parity of ’s. Strings of ’s interspersed with ’s. After an even number of ’s we need one more , then possibly more even-count additions:

This reads as: any number of ’s, then zero or more pairs of ’s (each pair maintaining even count) interleaved with ’s, then exactly one (making the total odd), then trailing ’s.

7. Strings ending with , not containing .

Since is forbidden, any must be immediately followed by (or be the last character, but the string must end in , so every must be followed by ). The pattern is: blocks of ’s, interleaved with single ’s each immediately followed by :

This generates all strings over where every is immediately followed by . All such strings end in (since the last character comes from or , both ending in ) and contain no .

8. Even number of ’s and even number of ’s.

We need to track parity of both -count and -count. Think of the four states: (even-, even-), (odd-, even-), (even-, odd-), (odd-, odd-). We want strings that start and end in state (even, even).

The regular expression is:

Interpretation: we build the string from blocks that preserve even parity on both counts. Each block is either (adds 2 to -count), (adds 2 to -count), or a pair of “cross” moves separated by optional even-blocks — which together contribute 1+1 to each count, keeping both parities even overall.

Answer: (5) ; (6) ; (7) ; (8) .

4.7. Construct NFSAs for Homework Languages (Lab 9, Task 7)

Construct NFSAs over and for each language below, then convert each to a DFSA.

1. . Example strings: , , .

Click to see the solution

: any is followed by at least one .

NFSA. We need to reject strings where a appears at the very end or is followed immediately by another without an intervening .

• (accepting, start): self-loop on ; transition to on .
• : transition to on (the required after the ); transition to (dead/rejecting) on (a immediately following another with no intervening ).
• (dead): self-loop on .

DFSA conversion. The NFSA is already nearly deterministic. The DFSA is identical; becomes the explicit trap state. and are the live states. Note that the empty string is accepted (start state is accepting).

: contains substring .

NFSA. A linear chain spelling out , with a self-loop at the start:

• : self-loop on ; transition to on .
• .
• (accepting): self-loop on .

DFSA conversion. Apply subset construction. The resulting DFSA has up to states in the worst case, but due to the failure-function structure (similar to KMP), most states collapse. In practice the DFSA has 8 states corresponding to the longest proper suffix of that is also a prefix of .

: and last two symbols are the same.

NFSA. The machine guesses when the second-to-last symbol starts:

• : self-loop on ; transition to on ; transition to on .
• : transition to (accepting) on (last two were ).
• : transition to (accepting) on (last two were ).
• : accepting state (no outgoing transitions — the match is complete).

DFSA conversion. Apply subset construction starting from :

DFSA state	on	on

: strings containing exactly 5 zeros.

NFSA. Count zeros with states through , each with a self-loop on , and a transition on to the next state. After (accepting), reject any additional :

• for : self-loop on ; transition to on .
• (accepting): self-loop on ; transition to (dead) on .
• (dead): self-loop on .

DFSA conversion. This NFSA is already deterministic — the transition function is single-valued. The DFSA equals the NFSA directly (7 states: through active, dead).

Answer: NFSAs and DFSAs as described above for each of the four languages.

4.8. Prove Closure of NFSA Languages under Complement (Lecture 9, Task 1)

Is the class of languages recognized by NFSAs closed under complement? Provide a formal proof.

Click to see the solution

Claim: Yes, the class of languages recognized by NFSAs is closed under complement.

Proof.

Let be a language recognized by some NFSA . We want to show that is also recognized by some finite automaton.

Step 1 — Convert NFSA to DFSA.

By the subset construction theorem, every NFSA is equivalent to some DFSA that recognizes the same language . That is, .

Step 2 — Complement the DFSA.

Given a complete (total) DFSA , construct a new DFSA by swapping the accepting and non-accepting states. Since is total (every state has a transition for every input symbol), is also a valid complete DFSA.

Step 3 — Verify correctness.

For any string :

• accepts iff .
• accepts iff , i.e., .

Therefore accepts exactly those strings that rejects:

Since is a DFSA (in particular, an NFSA), is recognized by an NFSA.

Conclusion. The class of NFSA-recognized languages (= regular languages) is closed under complement.

Why this argument does not work directly for NFSAs. The complement trick (swap and ) does not work directly on an NFSA, because an NFSA accepts if any branch accepts. Swapping accepting states would yield a machine that rejects if any branch rejects — i.e., accepts only if all branches accept (universal nondeterminism), which is a different semantics. The correctness of the argument relies critically on going through the deterministic construction first.

4.9. Verify Requires a Turing Machine (Lecture 9, Example 1)

Explain why the language cannot be recognized by any PDA, and describe the Turing Machine solution.

Click to see the solution

Why PDAs fail. A PDA can recognize by pushing one stack symbol per and popping one per . But after matching all ’s, the stack is empty — the count of has been destroyed. There are no remaining stack symbols to count the ’s. Formally, is not a context-free language (proven by the Pumping Lemma for context-free languages).

TM solution using one memory tape.

The TM uses the memory tape to store marker symbols :

1. State (initialization): Read the first and the initial symbol on the memory tape. Move: input stays, memory tape moves right (). Go to .
2. State (counting ’s): Self-loop: for each read, write on the memory tape and advance both heads rightward (). When the input shows : stay on input, move memory head left (); go to .
3. State (matching ’s): Self-loop: for each read, read (still present) on memory tape, advance input right but move memory left (). When input shows and memory shows : stay on input, move memory right (); go to .
4. State (matching ’s): Self-loop: for each read, read on memory tape, advance both rightward. When input is blank and memory is blank: stay (); go to (accepting).

Key insight: The markers persist on the memory tape. They are read but not erased during the -counting phase (the head merely moves backward over them); they are available again for the -counting phase when the head moves forward once more.

Answer: A TM recognizes precisely because its tape memory is non-destructive, allowing the count to be verified twice.

4.10. Compare NFSA and DFSA for Strings Ending in 00 (Tutorial 9, Example 1)

Construct both an NFSA and a DFSA accepting all binary strings ending with , over .

Click to see the solution

Key Concept: The DFSA must explicitly track all possible “suffixes in progress,” leading to more states. The NFSA can “guess” when the final begins.

DFSA approach. The machine must remember the last two symbols seen:

• : last symbol was (or start) — self-loop on ; go to on .
• : last symbol was — go back to on ; go to on .
• (accepting): last two symbols were — self-loop on ; go back to on .

DFSA accepting strings ending in 00

NFSA approach. Much simpler — the machine “guesses” when the last starts:

• : self-loop on ; go to on (guess this is the start of the final ).
• : go to accepting on .

NFSA accepting strings ending in 00 (3 states vs. 3 states with fewer transitions)

Answer: The NFSA uses the same number of states here but has far fewer transitions. For longer patterns the advantage becomes exponential.

4.11. Convert NFSA to DFSA via Subset Construction (Tutorial 9, Example 2)

Given the NFSA for strings ending in (from Example 4.1 above), apply the subset construction to produce an equivalent DFSA.

NFSA transition table:

Click to see the solution

Step 1. Start with DFSA state .

Step 2. Compute transitions from :

• On : → new DFSA state
• On : → DFSA state (already known)

Step 3. Compute transitions from :

• On : → new state
• On :

Step 4. Compute transitions from :

• On :
• On :

No new states. The DFSA transition table is:

is accepting because it contains .

Answer: The DFSA has 3 states, matching the DFSA from Example 4.1 (the states , , ).

4.12. Apply Thompson’s Construction to (Tutorial 9, Example 3)

Build an -NFSA for the regular expression using Thompson’s Construction, then simplify by removing redundant -transitions.

Click to see the solution

Step 1 — Build : Two states .

Step 2 — Build and for the concatenation : and . Connect via to get : .

Step 3 — Union : Create new start and new accepting . * (into ), * (into ),

Step 4 — Kleene star : Create new start and new accepting . * (bypass for zero repetitions) * (enter the union) * (loop back) * (exit)

Step 5 — Simplify. After -elimination, the resulting simplified NFSA has:

• A single start/accepting state (which also plays the role of ).
• (read a directly).
• (an intermediate state), then (read ).
• (loop for repetition, or equivalently is identified with after simplification).

Answer: The simplified NFSA accepts any concatenation of strings from , including the empty string. The machine collapses to a compact form with start/accept coinciding.